import math
A = [1]
B = [0]
for n in range(4,62,2):
A.append((B[-1]+math.comb(n-1,n//2-1))%998244353)
B.append((math.comb(n,n//2)-A[-1]-1)%998244353)
t = int(input())
for _ in range(t):
n = int(input())
ind = n//2-1
print(str(A[ind])+" "+str(B[ind])+" "+"1")#include <bits/stdc++.h>
using namespace std;
const int N=70;
const int mod=998244353;
long long c[N][N];
void init(){
c[1][1]=1;
for(int i=1;i<=65;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
}
void solved(){
int n;
cin>>n;
std::vector<long long > dp(n+1),b(n+1);
dp[2]=1;
b[2]=0;
for(int i=4;i<=n;i+=2){
dp[i]=c[i-2][i/2-2]+c[i-2][(i-2)/2]+b[i-2];
dp[i]%=mod;
b[i]=(c[i][i/2]-dp[i]-1+mod)%mod;
b[i]%=mod;
}
cout<<dp[n]<<" "<<b[n]<<" "<<1<<endl;
}
int main(){
ios::sync_with_stdio(false );
cin.tie(0);
cout.tie(0);
int t;
init();
cin>>t;
while(t--) solved();
}305B - Continued Fractions | 1165B - Polycarp Training |
1646C - Factorials and Powers of Two | 596A - Wilbur and Swimming Pool |
1462B - Last Year's Substring | 1608B - Build the Permutation |
1505A - Is it rated - 2 | 169A - Chores |
765A - Neverending competitions | 1303A - Erasing Zeroes |
1005B - Delete from the Left | 94A - Restoring Password |
1529B - Sifid and Strange Subsequences | 1455C - Ping-pong |
1644C - Increase Subarray Sums | 1433A - Boring Apartments |
1428B - Belted Rooms | 519B - A and B and Compilation Errors |
1152B - Neko Performs Cat Furrier Transform | 1411A - In-game Chat |
119A - Epic Game | 703A - Mishka and Game |
1504C - Balance the Bits | 988A - Diverse Team |
1312B - Bogosort | 1616B - Mirror in the String |
1660C - Get an Even String | 489B - BerSU Ball |
977C - Less or Equal | 1505C - Fibonacci Words |